// 给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。

// 示例 1:

// 输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
// 输出: 16 
// 解释: 这两个单词为 "abcw", "xtfn"。
// 示例 2:

// 输入: ["a","ab","abc","d","cd","bcd","abcd"]
// 输出: 4 
// 解释: 这两个单词为 "ab", "cd"。
// 示例 3:

// 输入: ["a","aa","aaa","aaaa"]
// 输出: 0 
// 解释: 不存在这样的两个单词。

#include "../stdc++.h"

/* 优化的方法 noCommonLetters：简单方法
时间复杂度：O(n^2 * L1*L2)
空间复杂度：O(1)
*/
class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size();
        int res{0};
        for (int i{0}; i < n; ++i) {
            for (int j{i + 1}; j < n; ++j) {
                if (noCommonLetters(words[i], words[j])) {
                    res = max(res, static_cast<int>(words[i].size() * words[j].size()));
                }
            }
        }
        return res;
    }
    bool noCommonLetters(const string& s1, const string& s2) {
        for (const char& c : s1) {
            if (s2.find(c) != -1) return false;
        }
        return true;
    }
};

/* 优化的方法 noCommonLetters：位操作
时间复杂度：O(n^2 * L1+L2)
空间复杂度：O(1)
*/
class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size();
        int res{0};
        for (int i{0}; i < n; ++i) {
            for (int j{i + 1}; j < n; ++j) {
                if (noCommonLetters(words[i], words[j])) {
                    res = max(res, static_cast<int>(words[i].size() * words[j].size()));
                }
            }
        }
        return res;
    }
    bool noCommonLetters(const string& s1, const string& s2) {
        int bitMask1{0};
        int bitMask2{0};
        for (const char& c : s1) {
            bitMask1 |= 1 << (c - 'a');
        }
        for (const char& c : s2) {
            bitMask2 |= 1 << (c - 'a');
        }
        return (bitMask1 & bitMask2) == 0;
    }
};

/* 优化的方法 noCommonLetters：位操作+预计算
使用O(1)的时间比较
时间复杂度：O(n^2 + L)
空间复杂度：O(N)
*/
class Solution {
public:
    int maxProduct(vector<string>& words) {
        int n = words.size();
        vector<int> masks(n, 0);
        for (int i{0}; i < n; ++i) {
            for (const char& c : words[i]) {
                masks[i] |= (1 << (c - 'a'));
            }
        }
        int res{0};
        for (int i{0}; i < n; ++i) {
            for (int j{i + 1}; j < n; ++j) {
                if ((masks[i] & masks[j]) == 0) {
                    res = max(res, static_cast<int>(words[i].size() * words[j].size()));
                }
            }
        }
        return res;
    }
};

/* 优化的方法 noCommonLetters：位操作+预计算
使用O(1)的时间比较
时间复杂度：O(n^2 + L)
空间复杂度：O(N)
*/
class Solution {
public:
    int maxProduct(vector<string>& words) {
        unordered_map<int, int> hashMap{};
        for (const string& word : words) {
            int mask{0};
            for (const char& c : word) {
                mask |= (1 << (c - 'a'));
            }
            // 对于有相同的字母，但是长度不同的，取最长的存放在哈希表中
            hashMap[mask] = max(hashMap[mask], static_cast<int>(word.size()));
        }
        int res{0};
        for (const auto& p0 : hashMap) {
            for (const auto& p1 : hashMap) {
                if ((p0.first & p1.first) == 0) {
                    res = max(res, p0.second * p1.second);
                }
            }
        }
        return res;
    }
};